{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers #divide-and-conquer #sorting #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针 #分治 #排序 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #排序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你链表的头结点&nbsp;<code>head</code>&nbsp;，请将其按 <strong>升序</strong> 排列并返回 <strong>排序后的链表</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg\" style=\"width: 450px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>head = [4,2,1,3]\n",
    "<b>输出：</b>[1,2,3,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg\" style=\"width: 550px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>head = [-1,5,3,4,0]\n",
    "<b>输出：</b>[-1,0,3,4,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>head = []\n",
    "<b>输出：</b>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目在范围&nbsp;<code>[0, 5 * 10<sup>4</sup>]</code>&nbsp;内</li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>进阶：</b>你可以在&nbsp;<code>O(n&nbsp;log&nbsp;n)</code> 时间复杂度和常数级空间复杂度下，对链表进行排序吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-list](https://leetcode.cn/problems/sort-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-list](https://leetcode.cn/problems/sort-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,1,3]', '[-1,5,3,4,0]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next: return head\n",
    "        p1, p2 = head, head.next\n",
    "        while p2 and p2.next:\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next.next\n",
    "        head1, head2 = head, p1.next\n",
    "        p1.next = None\n",
    "        head1 = self.sortList(head1)\n",
    "        head2 = self.sortList(head2)\n",
    "        dummy = ListNode(0)\n",
    "        cur, p1, p2 = dummy, head1, head2\n",
    "        while p1 and p2:\n",
    "            if p1.val <= p2.val:\n",
    "                cur.next = p1\n",
    "                p1 = p1.next\n",
    "            else:\n",
    "                cur.next = p2\n",
    "                p2 = p2.next\n",
    "            cur = cur.next\n",
    "        cur.next = p1 or p2\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if (not head) or (not head.next):\n",
    "            return head\n",
    "        \n",
    "        fast,slow,prev=head,head,head\n",
    "        \n",
    "        while fast and fast.next:\n",
    "            prev=slow\n",
    "            fast=fast.next.next\n",
    "            slow=slow.next\n",
    "            \n",
    "        prev.next=None\n",
    "        \n",
    "        return self.merge(self.sortList(head),self.sortList(slow))\n",
    "        \n",
    "    def merge(self,l1,l2):\n",
    "        head=ListNode(0)\n",
    "        pre=head\n",
    "        \n",
    "        while l1 and l2:\n",
    "            if l1.val<l2.val:\n",
    "                pre.next=l1\n",
    "                l1,pre=l1.next,pre.next\n",
    "            else:\n",
    "                pre.next=l2\n",
    "                l2,pre=l2.next,pre.next\n",
    "                \n",
    "        if l1:\n",
    "            pre.next=l1\n",
    "        if l2:\n",
    "            pre.next=l2\n",
    "            \n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        def mergeSort(prev, merge_size):\n",
    "            l = prev.next\n",
    "            msize = merge_size // 2\n",
    "            r = l\n",
    "            while msize:\n",
    "                r = r.next\n",
    "                if r == None:\n",
    "                    break\n",
    "                msize -= 1\n",
    "            # it's the last segment\n",
    "            if r == None:\n",
    "                return None\n",
    "            \n",
    "            l_size = r_size = merge_size // 2\n",
    "            while l_size > 0 and r_size > 0 and r:\n",
    "                if l.val < r.val:\n",
    "                    prev.next, l = l, l.next\n",
    "                    l_size -= 1\n",
    "                else:\n",
    "                    prev.next, r = r, r.next\n",
    "                    r_size -= 1\n",
    "                prev = prev.next\n",
    "            \n",
    "            while l_size > 0:\n",
    "                prev.next, l = l, l.next\n",
    "                prev = prev.next\n",
    "                l_size -= 1\n",
    "                \n",
    "            while r_size > 0 and r:\n",
    "                prev.next, r = r, r.next\n",
    "                prev = prev.next\n",
    "                r_size -= 1\n",
    "\n",
    "            # it's important\n",
    "            prev.next = r\n",
    "                \n",
    "            # it's the last segment\n",
    "            if r_size and not r:\n",
    "                return None\n",
    "            return prev\n",
    "        \n",
    "        size = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            size += 1\n",
    "        \n",
    "        new_head = ListNode(-1)\n",
    "        prev = new_head\n",
    "        prev.next = head\n",
    "        merge_size = 2\n",
    "        while merge_size < size * 2:\n",
    "            while prev and prev.next:\n",
    "                prev = mergeSort(prev, merge_size)\n",
    "            merge_size *= 2\n",
    "            prev = new_head\n",
    "\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head):\n",
    "        t=[]\n",
    "        tt=head\n",
    "        res=head\n",
    "        while head:\n",
    "            t.append(head.val)\n",
    "            head=head.next\n",
    "        t.sort()\n",
    "        for i in t:\n",
    "            tt.val=i\n",
    "            tt=tt.next\n",
    "        return res\n",
    "        \n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        mid = self.get_mid(head)\n",
    "        l = head\n",
    "        r = mid.next\n",
    "        print(l.val)\n",
    "        \n",
    "        mid.next = None\n",
    "        print(r.val)\n",
    "        return self.merge(self.sortList(l), self.sortList(r))\n",
    "\n",
    "    def merge(self, p, q):\n",
    "            tmp = ListNode(0)\n",
    "            h = tmp\n",
    "            while p and q:\n",
    "                if p.val < q.val:\n",
    "                    h.next = p\n",
    "                    p = p.next\n",
    "                else:\n",
    "                    h.next = q\n",
    "                    q = q.next\n",
    "                h = h.next\n",
    "            if p:\n",
    "                h.next = p\n",
    "            if q:\n",
    "                h.next = q\n",
    "            return tmp.next\n",
    "\n",
    "    def get_mid(self, node):\n",
    "        if node is None:\n",
    "            return node\n",
    "        fast = slow = node\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "        L = []\n",
    "        while head:\n",
    "            L.append((head.val, head))\n",
    "            head = head.next\n",
    "        \n",
    "        L.sort(key=lambda x: x[0])\n",
    "        head = L.pop(0)[1]\n",
    "        p = head\n",
    "        while L:\n",
    "            p.next = L.pop(0)[1]\n",
    "            p = p.next\n",
    "        p.next = None\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        pre.next = None\n",
    "        return self.mergeTwoLists(self.sortList(head), self.sortList(slow))\n",
    "    \n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        dummy_l0 = ListNode(0)\n",
    "        curr = dummy_l0\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                curr.next = ListNode(l1.val)\n",
    "                curr = curr.next\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                curr.next = ListNode(l2.val)\n",
    "                curr = curr.next\n",
    "                l2 = l2.next\n",
    "        if l2:\n",
    "            curr.next = l2\n",
    "        else:\n",
    "            curr.next = l1\n",
    "        return dummy_l0.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return []\n",
    "        length = 0\n",
    "        temp = head\n",
    "        while temp!=None:\n",
    "            length += 1\n",
    "            temp = temp.next\n",
    "        # print(length)\n",
    "        def fun(node, l):\n",
    "            if l == 1:\n",
    "                return node\n",
    "            p = node\n",
    "            mid = l // 2\n",
    "            for i in range(mid-1):\n",
    "                p = p.next\n",
    "            mid_p = p.next\n",
    "            p.next = None\n",
    "            left = fun(node, mid)\n",
    "            right = fun(mid_p, l-mid)\n",
    "            prev = ListNode(0)\n",
    "            root = prev\n",
    "            left_count = 0\n",
    "            right_count = 0\n",
    "            while left_count<mid and right_count<l-mid:\n",
    "                if left.val <= right.val:\n",
    "                    prev.next = left\n",
    "                    left = left.next\n",
    "                    left_count += 1\n",
    "                else:\n",
    "                    prev.next = right\n",
    "                    right = right.next\n",
    "                    right_count += 1\n",
    "                prev = prev.next\n",
    "            if mid != left_count:\n",
    "                prev.next = left\n",
    "            elif right_count != l-mid:\n",
    "                prev.next = right\n",
    "            else:\n",
    "                prev.next = None\n",
    "            return root.next\n",
    "        return fun(head, length)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next: \n",
    "            return head\n",
    "        slow = head\n",
    "        fast = head\n",
    "        # 用快慢指针分成两部分\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        # 找到左右部分, 把左部分最后置空\n",
    "        mid = slow.next\n",
    "        slow.next = None\n",
    "        # 递归下去\n",
    "        left = self.sortList(head)\n",
    "        right = self.sortList(mid)\n",
    "        # 合并\n",
    "        return self.merge(left, right)\n",
    "\n",
    "    def merge(self, left, right):\n",
    "        dummy = ListNode(0)\n",
    "        p = dummy\n",
    "        l = left\n",
    "        r = right\n",
    "\n",
    "        while l and r:\n",
    "            if l.val < r.val:\n",
    "                p.next = l\n",
    "                l = l.next\n",
    "                p = p.next\n",
    "            else:\n",
    "                p.next = r\n",
    "                r = r.next\n",
    "                p = p.next\n",
    "        if l:\n",
    "            p.next = l\n",
    "        if r:\n",
    "            p.next = r\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        l = []\n",
    "        temp = head\n",
    "        while temp:\n",
    "            l.append(temp.val)\n",
    "            temp = temp.next\n",
    "        l.sort()\n",
    "        head.val = l[0]\n",
    "        temp = head\n",
    "        for i in range(1,len(l)):\n",
    "            temp.next.val = l[i]\n",
    "            temp = temp.next\n",
    "        return head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "    def traverse(self):\n",
    "        p = self\n",
    "        while p:\n",
    "            print(p.val)\n",
    "            p = p.next\n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def from_list(self, nums: list):\n",
    "        p = self.head = None\n",
    "        for n in nums:\n",
    "            if not self.head:\n",
    "                self.head = p = ListNode(n)\n",
    "            else:\n",
    "                p.next = ListNode(n)\n",
    "                p = p.next\n",
    "\n",
    "    def traverse(self):\n",
    "        p = self.head\n",
    "        while p:\n",
    "            print(p.val)\n",
    "            p = p.next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        def merge_sort(head, length):\n",
    "            if length <= 1:\n",
    "                return head\n",
    "            m = length // 2\n",
    "            prev_p, p = None, head\n",
    "            for _ in range(m):\n",
    "                prev_p, p = p, p.next\n",
    "            prev_p.next = None\n",
    "\n",
    "            h1 = merge_sort(head, m)\n",
    "            h2 = merge_sort(p, length - m)\n",
    "            h3 = merge(h1, h2)\n",
    "            return h3\n",
    "\n",
    "        def merge(h1, h2):\n",
    "            h3 = p = ListNode()\n",
    "            while h1 and h2:\n",
    "                if h1.val < h2.val:\n",
    "                    p.next = h1\n",
    "                    h1 = h1.next\n",
    "                else:\n",
    "                    p.next = h2\n",
    "                    h2 = h2.next\n",
    "                p = p.next\n",
    "            if h1:\n",
    "                p.next = h1\n",
    "            if h2:\n",
    "                p.next = h2\n",
    "            return h3.next\n",
    "\n",
    "        length, p = 0, head\n",
    "        while p:\n",
    "            length += 1\n",
    "            p = p.next\n",
    "        return merge_sort(head, length)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        id2val = {}\n",
    "        while head:\n",
    "            id2val[head] = head.val\n",
    "            head = head.next\n",
    "        id2val_sorted = sorted(id2val.items(), key=lambda item:item[1])\n",
    "        p = dummy = ListNode()\n",
    "        for id, val in id2val_sorted:\n",
    "            p.next = id\n",
    "            p = p.next\n",
    "        p.next = None\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        mid = slow.next\n",
    "        slow.next = None\n",
    "        left = self.sortList(head)\n",
    "        right = self.sortList(mid)\n",
    "        return self.merge(left,right)\n",
    "    def merge(self,l1,l2):\n",
    "        p = ListNode(0)\n",
    "        q = p\n",
    "        while l1 and l2:\n",
    "            if l1.val<l2.val:\n",
    "                p.next = ListNode(l1.val)\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                p.next = ListNode(l2.val)\n",
    "                l2 = l2.next\n",
    "            p = p.next\n",
    "        p.next = l1 or l2\n",
    "        return q.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def merge_sort(left, right):\n",
    "            if left == right: return left\n",
    "            mid = get_mid(left, right)\n",
    "            mid_next = mid.next\n",
    "            mid.next = None\n",
    "            return merge(merge_sort(left, mid), merge_sort(mid_next, right))\n",
    "        \n",
    "        def merge(left, right):\n",
    "            head = ListNode(0)\n",
    "            head_ = head\n",
    "            while left and right:\n",
    "            # 2->4->1->3\n",
    "                if left.val > right.val:\n",
    "                    head.next = ListNode(right.val)\n",
    "                    right = right.next\n",
    "                else:\n",
    "                    head.next = ListNode(left.val)\n",
    "                    left = left.next\n",
    "                head = head.next\n",
    "\n",
    "            if left:\n",
    "                head.next = left\n",
    "            if right:\n",
    "                head.next = right\n",
    "\n",
    "            return head_.next\n",
    "        \n",
    "        def get_mid(left,right):\n",
    "            mid = left\n",
    "            counter = 0\n",
    "            while left!=right:\n",
    "                left = left.next\n",
    "                counter += 1\n",
    "            counter //= 2\n",
    "            while counter:\n",
    "                mid = mid.next\n",
    "                counter -=1\n",
    "            return mid\n",
    "\n",
    "        if head is None: return None\n",
    "        left = head\n",
    "        while head.next:\n",
    "            head = head.next\n",
    "        return merge_sort(left, head)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next: return head\n",
    "        slow, fast = head, head.next\n",
    "        while fast and fast.next:\n",
    "            fast, slow = fast.next.next, slow.next\n",
    "\n",
    "        right = self.sortList(slow.next)\n",
    "        slow.next = None\n",
    "        left = self.sortList(head)\n",
    "\n",
    "        res = ListNode(0)\n",
    "        curr = right\n",
    "        curl = left\n",
    "        curres = res\n",
    "        while curr and curl:\n",
    "            if curr.val<curl.val:\n",
    "                curres.next = ListNode(curr.val)\n",
    "                curr = curr.next\n",
    "            else:\n",
    "                curres.next = ListNode(curl.val)\n",
    "                curl = curl.next\n",
    "            curres = curres.next\n",
    "        curres.next = curr if curr else curl\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def _get_list(head):\n",
    "            res = []\n",
    "            while head:\n",
    "                res.append(head.val)\n",
    "                head = head.next\n",
    "            return res\n",
    "        \n",
    "        val_list = _get_list(head)\n",
    "\n",
    "        val_list = sorted(val_list)\n",
    "\n",
    "        def _get_node(val_list):\n",
    "            tmp = ListNode(0)\n",
    "            cur = tmp\n",
    "            while val_list:\n",
    "                node = val_list.pop(0)\n",
    "                cur.next = ListNode(node)\n",
    "                cur = cur.next\n",
    "            cur.next = None\n",
    "            return tmp.next\n",
    "\n",
    "        return _get_node(val_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        node=head.next\n",
    "        pre=head\n",
    "        while node:\n",
    "            if node.val>=pre.val:\n",
    "                pre=node\n",
    "                node=node.next\n",
    "            else:\n",
    "                pre.next=node.next\n",
    "                if node.val<head.val:\n",
    "                    node.next=head\n",
    "                    head=node\n",
    "                else:\n",
    "                    temp=head\n",
    "                    while temp.next.val<node.val:\n",
    "                        temp=temp.next\n",
    "                    node.next=temp.next\n",
    "                    temp.next=node\n",
    "                node=pre.next\n",
    "        return head\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return \n",
    "\n",
    "        dummyhead = ListNode(0)\n",
    "        dummyhead.next = head\n",
    "        lastorder = head\n",
    "        cur = head.next\n",
    "\n",
    "        while cur:\n",
    "            if cur.val >= lastorder.val:\n",
    "                lastorder = lastorder.next\n",
    "            else:\n",
    "                prev = dummyhead\n",
    "                while prev.next.val < cur.val:\n",
    "                    prev = prev.next\n",
    "                lastorder.next = cur.next\n",
    "                cur.next = prev.next\n",
    "                prev.next = cur\n",
    "            \n",
    "            cur = lastorder.next\n",
    "        \n",
    "        return dummyhead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        tail = self.get_tail(head)\n",
    "        return self.helper(head, tail)\n",
    "\n",
    "    \n",
    "    def helper(self, head, tail):\n",
    "        if head == tail:\n",
    "            return ListNode(head.val)\n",
    "\n",
    "        mid = self.get_mid(head, tail)\n",
    "        left = self.helper(head, mid)\n",
    "        right = self.helper(mid.next, tail)\n",
    "\n",
    "        return self.merge(left, right)\n",
    "\n",
    "    \n",
    "    def merge(self, left, right):\n",
    "        dummy = curt = ListNode(None)\n",
    "\n",
    "        while left and right:\n",
    "            if left.val < right.val:\n",
    "                curt.next = left\n",
    "                left = left.next\n",
    "            else:\n",
    "                curt.next = right\n",
    "                right = right.next\n",
    "            curt = curt.next\n",
    "\n",
    "        if left:\n",
    "            curt.next = left\n",
    "        else:\n",
    "            curt.next = right\n",
    "\n",
    "        return dummy.next\n",
    "\n",
    "    \n",
    "    def get_mid(self, head, tail):\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "        while fast != tail and fast.next != tail:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    "\n",
    "\n",
    "    def get_tail(self, head):\n",
    "        while head.next:\n",
    "            head = head.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:\n",
    "            if not head:\n",
    "                return head\n",
    "            if head.next == tail:\n",
    "                head.next = None\n",
    "                return head\n",
    "            slow = fast = head\n",
    "            while fast != tail:\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "                if fast != tail:\n",
    "                    fast = fast.next\n",
    "            mid = slow\n",
    "            return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "            \n",
    "        def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "            dummyHead = ListNode(0)\n",
    "            temp, temp1, temp2 = dummyHead, head1, head2\n",
    "            while temp1 and temp2:\n",
    "                if temp1.val <= temp2.val:\n",
    "                    temp.next = temp1\n",
    "                    temp1 = temp1.next\n",
    "                else:\n",
    "                    temp.next = temp2\n",
    "                    temp2 = temp2.next\n",
    "                temp = temp.next\n",
    "            if temp1:\n",
    "                temp.next = temp1\n",
    "            elif temp2:\n",
    "                temp.next = temp2\n",
    "            return dummyHead.next\n",
    "        \n",
    "        return sortFunc(head, None)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:return head\n",
    "        slow,fast = head,head.next\n",
    "        while fast and fast.next:\n",
    "            fast,slow = fast.next.next,slow.next\n",
    "        mid,slow.next = slow.next,None\n",
    "        left,right = self.sortList(head),self.sortList(mid)\n",
    "\n",
    "        pre = cur = ListNode(0)\n",
    "        while left and right:\n",
    "            if left.val<=right.val:cur.next,left = ListNode(left.val),left.next\n",
    "            else:cur.next,right = ListNode(right.val),right.next\n",
    "            cur = cur.next\n",
    "        cur.next = right if left==None else left\n",
    "        return pre.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:return head\n",
    "        slow,fast = head,head.next\n",
    "        while fast and fast.next:\n",
    "            fast,slow = fast.next.next,slow.next\n",
    "        mid,slow.next = slow.next,None\n",
    "        left,right = self.sortList(head),self.sortList(mid)\n",
    "\n",
    "        pre = cur = ListNode(0)\n",
    "        while left and right:\n",
    "            if left.val<=right.val:cur.next,left = left,left.next\n",
    "            else:cur.next,right = right,right.next\n",
    "            cur = cur.next\n",
    "        cur.next = right if left==None else left\n",
    "        return pre.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next: return head # termination.\n",
    "        # cut the LinkedList at the mid index.\n",
    "        slow, fast = head, head.next\n",
    "        while fast and fast.next:\n",
    "            fast, slow = fast.next.next, slow.next\n",
    "        mid, slow.next = slow.next, None # save and cut.\n",
    "        # recursive for cutting.\n",
    "        left, right = self.sortList(head), self.sortList(mid)\n",
    "        # merge `left` and `right` linked list and return it.\n",
    "        h = res = ListNode(0)\n",
    "        while left and right:\n",
    "            if left.val < right.val: h.next, left = left, left.next\n",
    "            else: h.next, right = right, right.next\n",
    "            h = h.next\n",
    "        h.next = left if left else right\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def binary(node,tail):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.next==tail:\n",
    "                node.next=None\n",
    "                return node\n",
    "            slow,fast=node,node\n",
    "            while fast!=tail:\n",
    "                fast=fast.next\n",
    "                slow=slow.next\n",
    "                if fast!=tail:\n",
    "                    # print('node',node,'tail',tail)\n",
    "                    fast=fast.next\n",
    "            mid=slow\n",
    "            return merge(binary(node,mid),binary(mid,tail))\n",
    "        def merge(node1,node2):\n",
    "            # print(node1,node2)\n",
    "            node=ListNode(-1)\n",
    "            temp,a,b=node,node1,node2\n",
    "            while a and b:\n",
    "                # print('in',a,b)\n",
    "                if a.val>=b.val:\n",
    "                    # print('in')\n",
    "                    temp.next=b\n",
    "                    # print('tem',temp)\n",
    "                    temp=temp.next\n",
    "                    b=b.next\n",
    "                else:\n",
    "                    temp.next=a\n",
    "                    temp=temp.next\n",
    "                    a=a.next\n",
    "            if a:\n",
    "                temp.next=a\n",
    "            if b:\n",
    "                temp.next=b\n",
    "            # print(node.next,temp)\n",
    "            return node.next\n",
    "\n",
    "        return binary(head,None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\"\"\"\n",
    "1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。\n",
    "2. 对两个子链表分别排序。\n",
    "3. 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:\n",
    "            if not head:\n",
    "                return head\n",
    "            if head.next == tail:\n",
    "                head.next = None\n",
    "                return head\n",
    "            slow = fast = head\n",
    "            while fast != tail:\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "                if fast != tail:\n",
    "                    fast = fast.next\n",
    "            mid = slow\n",
    "            return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "            \n",
    "        def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "            dummyHead = ListNode(0)\n",
    "            t, t1, t2 = dummyHead, head1, head2\n",
    "            while t1 and t2:\n",
    "                if t1.val < t2.val:\n",
    "                    t.next = t1\n",
    "                    t = t1\n",
    "                    t1 = t1.next\n",
    "                else:\n",
    "                    t.next = t2\n",
    "                    t = t2\n",
    "                    t2 = t2.next\n",
    "            if t1:\n",
    "                t.next = t1\n",
    "            if t2:\n",
    "                t.next = t2\n",
    "            return dummyHead.next\n",
    "\n",
    "        return sortFunc(head, None)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return head\n",
    "\n",
    "        nodes = []\n",
    "        while head:\n",
    "            nodes.append(head)\n",
    "            head = head.next\n",
    "        \n",
    "        nodes.sort(key=lambda x: -x.val)\n",
    "\n",
    "        head = nodes[0]\n",
    "        head.next = None\n",
    "        for node in nodes[1:]:\n",
    "            node.next = head\n",
    "            head = node\n",
    "        return head\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return head\n",
    "        node_list = []\n",
    "        while head:\n",
    "            node_list.append(head)\n",
    "            head = head.next\n",
    "        def merge_sort(node_list):\n",
    "            n = len(node_list)\n",
    "            if n<2:\n",
    "                return node_list\n",
    "            p = n//2\n",
    "            res = []\n",
    "            left_sort = merge_sort(node_list[:p])\n",
    "            right_sort = merge_sort(node_list[p:])\n",
    "            l = 0\n",
    "            r = 0\n",
    "            while l<len(left_sort) and r<len(right_sort):\n",
    "                if left_sort[l].val<right_sort[r].val:\n",
    "                    res.append(left_sort[l])\n",
    "                    l+=1\n",
    "                else:\n",
    "                    res.append(right_sort[r])\n",
    "                    r+=1\n",
    "            if l<len(left_sort):\n",
    "                res = res + left_sort[l:]\n",
    "            elif r<len(right_sort):\n",
    "                res = res + right_sort[r:]\n",
    "            return res\n",
    "        res = merge_sort(node_list)\n",
    "        prev = ListNode(0)\n",
    "        node = prev\n",
    "        for i in range(len(res)):\n",
    "            node.next = res[i]\n",
    "            node = res[i]\n",
    "        node.next = None\n",
    "        return prev.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compare(self, a, b):\n",
    "        return a.val - b.val\n",
    "    \n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        list = []\n",
    "        while head:\n",
    "            list.append(head)\n",
    "            head = head.next\n",
    "\n",
    "        list.sort(key=functools.cmp_to_key(self.compare))\n",
    "        head = list[0]\n",
    "\n",
    "        for i in range(len(list) - 1):\n",
    "            list[i].next = list[i + 1]\n",
    "        \n",
    "        list[-1].next = None\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "        valnodes = []\n",
    "        while head:\n",
    "            valnodes.append((head.val,head))\n",
    "            head = head.next\n",
    "        valnodes.sort(key=lambda x:x[0])\n",
    "        for i in range(len(valnodes)-1):\n",
    "            valnodes[i][1].next = valnodes[i+1][1]\n",
    "        valnodes[-1][1].next = None\n",
    "        return valnodes[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next: return head\n",
    "        first = head; second = head\n",
    "        while first.next and first.next.next:\n",
    "            first = first.next.next\n",
    "            second = second.next\n",
    "        right = self.sortList(second.next)\n",
    "        second.next = None; left = self.sortList(head)\n",
    "        if right and left.val > right.val: left,right = right,left\n",
    "        output_s = left\n",
    "        while left.next and right:\n",
    "            if left.next.val > right.val:\n",
    "                left.next = ListNode(right.val,left.next)\n",
    "                right = right.next\n",
    "            left = left.next\n",
    "        if not left.next: left.next = right\n",
    "        return output_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def merge(self,left,right):\n",
    "        head = temListNode = ListNode(0)\n",
    "        while left and right:\n",
    "            if left.val < right.val:\n",
    "                temListNode.next,left = left,left.next\n",
    "            else:\n",
    "                temListNode.next,right = right,right.next\n",
    "            temListNode = temListNode.next\n",
    "        temListNode.next = left if left else right\n",
    "        return head.next\n",
    "\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:return head\n",
    "        slow,fast = head,head.next\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        mid,slow.next = slow.next,None\n",
    "        res = self.merge(self.sortList(head),self.sortList(mid))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p = head\n",
    "        l = 0\n",
    "        while p:\n",
    "            p = p.next\n",
    "            l += 1\n",
    "        curlen = 1\n",
    "        dummy = ListNode(0, head)\n",
    "        while curlen < l:\n",
    "            cur = dummy.next\n",
    "            p = dummy\n",
    "            while cur:\n",
    "                left = cur\n",
    "                right = self.cut(curlen, cur)\n",
    "                cur = self.cut(curlen, right)\n",
    "                p.next = self.merge(left, right)\n",
    "                while p.next:\n",
    "                    p = p.next\n",
    "            curlen <<= 1\n",
    "\n",
    "        return dummy.next\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def cut(self, length, node):\n",
    "        for i in range(length - 1):\n",
    "            if node:\n",
    "                node = node.next\n",
    "            else:\n",
    "                return None\n",
    "        if not node:\n",
    "            return None\n",
    "        ret = node.next\n",
    "        node.next = None\n",
    "        return ret\n",
    "\n",
    "    def merge(self, l1, l2):\n",
    "        dummy = ListNode(0)\n",
    "        p = dummy\n",
    "        while l1 and l2:\n",
    "            if l1.val > l2.val:\n",
    "                p.next = l2\n",
    "                l2 = l2.next\n",
    "            else:\n",
    "                p.next = l1\n",
    "                l1 = l1.next\n",
    "            p = p.next\n",
    "        if l1:\n",
    "            p.next = l1\n",
    "        if l2:\n",
    "            p.next = l2\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head:\n",
    "            if head.next is None:\n",
    "                return head\n",
    "            length = 0\n",
    "            cur = head\n",
    "            while cur:\n",
    "                length += 1\n",
    "                cur = cur.next\n",
    "            sublength = 1\n",
    "            cur_head = head\n",
    "            while sublength <= length:\n",
    "                res_head = res_tail = ListNode(None)\n",
    "                head1 = cur_head\n",
    "                while head1:\n",
    "                    head2 = self.get_firstN(head1, sublength)\n",
    "                    new_head1 = self.get_firstN(head2, sublength)\n",
    "                    head3, tail3 = self.merge(head1, head2)\n",
    "                    res_tail.next, res_tail = head3, tail3\n",
    "                    head1 = new_head1\n",
    "                cur_head = res_head.next\n",
    "                sublength = sublength * 2\n",
    "            return cur_head\n",
    "\n",
    "    def get_firstN(self, head, n):\n",
    "        cur = head\n",
    "        cnt = 0\n",
    "        next_head = None\n",
    "        while cur and cnt < n:\n",
    "            cnt += 1\n",
    "            if cnt == n:\n",
    "                tail, next_head = cur, cur.next\n",
    "                tail.next = None\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return next_head\n",
    "\n",
    "    def get_tail(self, head):\n",
    "        cur = tail = head\n",
    "        while cur:\n",
    "            tail, cur = cur, cur.next\n",
    "        return tail\n",
    "\n",
    "    def merge(self, list1, list2):\n",
    "        head = tail = ListNode(None)\n",
    "        cur1, cur2 = list1, list2\n",
    "        while cur1 and cur2:\n",
    "            if cur1.val <= cur2.val:\n",
    "                tail.next, cur1, tail = cur1, cur1.next, cur1\n",
    "            else:\n",
    "                tail.next, cur2, tail = cur2, cur2.next, cur2\n",
    "\n",
    "        tail.next = cur1 if cur1 else cur2\n",
    "        tail = self.get_tail(cur1 if cur1 else cur2)\n",
    "\n",
    "        return head.next, tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        # 将整个链表一分为2，进行merge_sort，最后进行merge\n",
    "\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        fastPoint = slowPoint = head\n",
    "        while fastPoint and fastPoint.next and  fastPoint.next.next:\n",
    "            fastPoint = fastPoint.next.next\n",
    "            slowPoint = slowPoint.next\n",
    "        rightHead = slowPoint.next\n",
    "        slowPoint.next = None\n",
    "\n",
    "        left = self.sortList(head)\n",
    "        right = self.sortList(rightHead)\n",
    "        return self.merge(left, right)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def merge(self, left, right):\n",
    "        dumy = ListNode(0)\n",
    "        p = dumy\n",
    "        while left and right:\n",
    "            if left.val <= right.val:\n",
    "                p.next = left\n",
    "                left = left.next\n",
    "            else:\n",
    "                p.next = right\n",
    "                right = right.next\n",
    "            p = p.next\n",
    "        if left:\n",
    "            p.next = left\n",
    "        if right:\n",
    "            p.next = right\n",
    "        return dumy.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        node = head\n",
    "        \n",
    "        nums = []\n",
    "        while node:\n",
    "            nums.append(node.val)\n",
    "            node = node.next\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        cur = head\n",
    "        for num in nums:\n",
    "            cur.val = num\n",
    "            cur = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def sort(head, tail):\n",
    "            if not head:\n",
    "                return head\n",
    "            if head.next == tail:\n",
    "                head.next = None\n",
    "                return head\n",
    "            slow = fast = head\n",
    "            while fast != tail:\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "                if fast != tail:\n",
    "                    fast = fast.next\n",
    "            return self.merge(sort(head, slow), sort(slow, tail))\n",
    "        return sort(head, None)\n",
    "\n",
    "    def merge(self, list1, list2):\n",
    "        prehead = ListNode(-1)\n",
    "        cur = prehead\n",
    "        while list1 and list2:\n",
    "            if list1.val < list2.val:\n",
    "                cur.next = list1\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                cur.next = list2\n",
    "                list2 = list2.next\n",
    "        \n",
    "            cur = cur.next\n",
    "        cur.next = list1 if list1 else list2\n",
    "        return prehead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "    # def __init__(self,val = 0,next = None):\n",
    "    #     self.val = val\n",
    "    #     self.next = next\n",
    "        \n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def FindMid(head,tail):\n",
    "            if head is None:\n",
    "                return head\n",
    "            if head.next == tail:\n",
    "                head.next = None\n",
    "                return head\n",
    "            slow = fast = head\n",
    "            \n",
    "            while fast != tail:\n",
    "                slow = slow.next \n",
    "                fast = fast.next\n",
    "                if fast!= tail:\n",
    "                    fast = fast.next \n",
    "            mid = slow\n",
    "            \n",
    "            return merge(FindMid(head,mid),FindMid(mid,tail))\n",
    "        \n",
    "        def merge(list1,list2):\n",
    "            dummy = ListNode(0)\n",
    "            p = dummy\n",
    "            l1 = list1\n",
    "            l2 = list2\n",
    "            \n",
    "            while l1 and l2:\n",
    "                if l1.val <= l2.val:\n",
    "                    p.next = l1\n",
    "                    p = p.next\n",
    "                    l1 = l1.next\n",
    "                    \n",
    "                else:\n",
    "                    p.next = l2\n",
    "                    p = p.next \n",
    "                    l2 = l2.next \n",
    "                    \n",
    "                if l1:\n",
    "                    p.next = l1\n",
    "                if l2:\n",
    "                    p.next = l2\n",
    "                    \n",
    "            return dummy.next\n",
    "        return FindMid(head,None)\n",
    "                    \n",
    "         \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return None\n",
    "        cur = head\n",
    "        nums = []\n",
    "        while cur:\n",
    "            nums.append(cur.val)\n",
    "            cur = cur.next\n",
    "        nums = self.mergesort(nums)\n",
    "\n",
    "        dummy = ListNode(None)\n",
    "        dummy.next = head\n",
    "        i = 0\n",
    "        while head:\n",
    "            head.val = nums[i]\n",
    "            head=  head.next\n",
    "            i = i + 1\n",
    "\n",
    "        return dummy.next\n",
    "\n",
    "        \n",
    "\n",
    "    def merge(self, nums1, nums2):\n",
    "        nums = []\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(nums1) and j < len(nums2):\n",
    "            if nums1[i] < nums2[j]:\n",
    "                nums.append(nums1[i])\n",
    "                i = i + 1\n",
    "            else:\n",
    "                nums.append(nums2[j])\n",
    "                j = j + 1\n",
    "        if i == len(nums1) :\n",
    "            nums = nums + nums2[j:]\n",
    "        if j == len(nums2):\n",
    "            nums = nums + nums1[i:]\n",
    "        return nums\n",
    "\n",
    "    def mergesort(self, nums):\n",
    "        if len(nums) <= 1:\n",
    "            return nums\n",
    "\n",
    "        mid = len(nums)//2\n",
    "        left_nums = self.mergesort(nums[:mid])\n",
    "        right_nums = self.mergesort(nums[mid:])\n",
    "        res = self.merge(left_nums, right_nums)\n",
    "        return res\n",
    "    \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head: return head\n",
    "        arr = []\n",
    "        p = head\n",
    "        while p:\n",
    "            arr.append(p)\n",
    "            p = p.next\n",
    "        def quicksort(arr):\n",
    "            if len(arr) <= 1:\n",
    "                return arr\n",
    "            pivot = choice(arr)\n",
    "            left = [x for x in arr if x.val < pivot.val]\n",
    "            mid = [x for x in arr if x.val == pivot.val]\n",
    "            right = [x for x in arr if x.val > pivot.val]\n",
    "            return quicksort(left)+mid+quicksort(right)\n",
    "        arr = quicksort(arr)\n",
    "        for i in range(len(arr)-1):\n",
    "            arr[i].next = arr[i+1]\n",
    "        arr[len(arr)-1].next = None\n",
    "        return arr[0]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s = []\n",
    "        if not head:\n",
    "            return None\n",
    "        while head != None:\n",
    "            s.append(head)\n",
    "            head = head.next\n",
    "        s.sort(key=lambda x: -x.val)\n",
    "        res_head = ListNode()\n",
    "        tmp_head = res_head\n",
    "        while len(s) != 0:\n",
    "            tmp_head.next = s.pop()\n",
    "            tmp_head = tmp_head.next\n",
    "        tmp_head.next = None\n",
    "        return res_head.next\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import functools\n",
    "class Solution:\n",
    "    \n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        def cmp(id1, id2):\n",
    "            return id1.val - id2.val\n",
    "        \n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        nodeList = []\n",
    "        p = head\n",
    "        while p:\n",
    "            nodeList.append(p)\n",
    "            tmp = p\n",
    "            p = p.next\n",
    "            tmp.next = None\n",
    "        nodeList = sorted(nodeList, key=functools.cmp_to_key(cmp))\n",
    "        \n",
    "        for i in range(0, len(nodeList)-1):\n",
    "            nodeList[i].next = nodeList[i+1]\n",
    "        \n",
    "       \n",
    "        return nodeList[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "        lstpq = []\n",
    "        while(head):\n",
    "            lstpq.append((head.val, head))\n",
    "            head = head.next\n",
    "        lstpq.sort(key = lambda t:t[0], reverse = True)\n",
    "        _, pre = lstpq.pop()\n",
    "        headpre = ListNode(0, pre)\n",
    "        while(lstpq):\n",
    "            _, node = lstpq.pop()\n",
    "            pre.next = node\n",
    "            pre = pre.next\n",
    "        pre.next = None\n",
    "        return headpre.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(0, head)\n",
    "        arr = []\n",
    "        while dummy.next is not None:\n",
    "            dummy = dummy.next\n",
    "            arr.append([dummy.val, dummy])\n",
    "        arr.sort(key=lambda x: x[0])\n",
    "        res = ListNode(0)\n",
    "        temp = res\n",
    "        for i, d in arr:\n",
    "            temp.next = d\n",
    "            temp = temp.next\n",
    "        temp.next = None\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        res = []\n",
    "        while(head):\n",
    "            res.append([head, head.val])\n",
    "            head = head.next\n",
    "\n",
    "        s = sorted(res, key=lambda x:x[1])\n",
    "        dummy = ListNode()\n",
    "        #dummy.next = s[0][0]\n",
    "        p = dummy\n",
    "        for i in range(len(s)):\n",
    "            dummy.next = s[i][0]\n",
    "            dummy = dummy.next\n",
    "\n",
    "        dummy.next = None\n",
    "        return p.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p = head\n",
    "        nums = []\n",
    "        i=0\n",
    "        while p!=None:\n",
    "            nums.append((i,p.val))\n",
    "            p=p.next\n",
    "            i+=1\n",
    "        nums.sort(key = lambda u: u[1])\n",
    "        i=0\n",
    "        p=head\n",
    "        while p!=None:\n",
    "            p.val = nums[i][1]\n",
    "            p=p.next\n",
    "            i+=1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    # 选择排序，超时\n",
    "    # 一开始我想得过于复杂，在考虑如何交换两个节点得问题，想着如何取出，插入，交换\n",
    "    # 纯属思维定势了，交换val就ok了\n",
    "    def sectionSort(self,head):\n",
    "        # 已经排好链表的后一个\n",
    "        left=head\n",
    "        # 遍历，找到最小的一个插入到left的位置\n",
    "        while left:\n",
    "            _min=left\n",
    "            right=left\n",
    "            # 找到没有排序的最小值\n",
    "            while right:\n",
    "                if right.val<_min.val:\n",
    "                    _min=right\n",
    "                right=right.next\n",
    "            # 把最小值放进去\n",
    "            left.val,_min.val=_min.val,left.val\n",
    "            left=left.next\n",
    "        return head\n",
    "\n",
    "    # 计数排序\n",
    "    def countSort(self,head):\n",
    "        map={}\n",
    "        cur=head\n",
    "        _min,_max=0,0\n",
    "        while cur:\n",
    "            k=cur.val\n",
    "            map[k]=1 if k not in map.keys() else map[k]+1\n",
    "            _min,_max=min(_min,k),max(_max,k)\n",
    "            cur=cur.next\n",
    "        cur=head\n",
    "        for i in range(_min,_max+1):\n",
    "            if i in map.keys():\n",
    "                for _ in range(map[i]):\n",
    "                    cur.val=i\n",
    "                    cur=cur.next\n",
    "        return head\n",
    "\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # return self.sectionSort(head)\n",
    "        return self.countSort(head)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        pq = PriorityQueue()\n",
    "        index = 0\n",
    "        while head is not None:\n",
    "            pq.put([head.val, index, head])\n",
    "            head = head.next\n",
    "            index += 1\n",
    "        head = dummy\n",
    "        while not pq.empty():\n",
    "            _, _, node = pq.get()\n",
    "            head.next = node\n",
    "            head = head.next\n",
    "        head.next = None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(0, head)\n",
    "        arr = []\n",
    "        while dummy.next is not None:\n",
    "            dummy = dummy.next\n",
    "            arr.append([dummy.val, dummy])\n",
    "        arr.sort(key=lambda x: (len(x), x[0]))\n",
    "        res = ListNode(0)\n",
    "        temp = res\n",
    "        for i, d in arr:\n",
    "            temp.next = d\n",
    "            temp = temp.next\n",
    "        temp.next = None\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: \n",
    "        #方法1 遍历一边生成一个list，然后再生成一个新的链表\n",
    "        # preHead = ListNode(0)\n",
    "        # newList = preHead\n",
    "\n",
    "        # temp = []\n",
    "        # while head:\n",
    "        #     temp.append(head.val)\n",
    "        #     head = head.next\n",
    "        # temp.sort()\n",
    "  \n",
    "        # for i in range(len(temp)):\n",
    "        #     newList.next = ListNode(temp[i])\n",
    "        #     newList = newList.next\n",
    "        \n",
    "        # return preHead.next\n",
    "        \n",
    "        preHead = ListNode(0)\n",
    "        values = list()\n",
    "\n",
    "        while head:\n",
    "            values.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        values.sort()\n",
    "\n",
    "        pre = preHead\n",
    "        \n",
    "        for i in range(len(values)):\n",
    "            pre.next = ListNode(values[i])\n",
    "            pre = pre.next\n",
    "        \n",
    "        return preHead.next\n",
    "\n",
    "\n",
    "\n",
    "        # def sortFunc(head: ListNode, tail: ListNode) -> ListNode:\n",
    "        #     if not head:\n",
    "        #         return head\n",
    "        #     if head.next == tail:\n",
    "        #         head.next = None\n",
    "        #         return head\n",
    "        #     slow = fast = head\n",
    "        #     # slow 会过半\n",
    "        #     while fast != tail:\n",
    "        #         slow = slow.next\n",
    "        #         fast = fast.next\n",
    "        #         if fast != tail:\n",
    "        #             fast = fast.next\n",
    "        #     mid = slow\n",
    "        #     return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "\n",
    "        # def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "        #     preHead = ListNode(0)\n",
    "        #     temp, temp1, temp2 = preHead, head1, head2\n",
    "        #     while temp1 and temp2:\n",
    "        #         if temp1.val <= temp2.val:\n",
    "        #             temp.next = temp1\n",
    "        #             temp1 = temp1.next\n",
    "        #         else:\n",
    "        #             temp.next = temp2\n",
    "        #             temp2 = temp2.next\n",
    "        #         temp = temp.next\n",
    "        #     if temp1:\n",
    "        #         temp.next = temp1\n",
    "        #     elif temp2:\n",
    "        #         temp.next = temp2\n",
    "        #     return preHead.next\n",
    "        \n",
    "        return sortFunc(head, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: \n",
    "        #方法1 遍历一边生成一个list，然后再生成一个新的链表\n",
    "        # preHead = ListNode(0)\n",
    "        # newList = preHead\n",
    "\n",
    "        # temp = []\n",
    "        # while head:\n",
    "        #     temp.append(head.val)\n",
    "        #     head = head.next\n",
    "        # temp.sort()\n",
    "  \n",
    "        # for i in range(len(temp)):\n",
    "        #     newList.next = ListNode(temp[i])\n",
    "        #     newList = newList.next\n",
    "        \n",
    "        # return preHead.next\n",
    "        \n",
    "        preHead = ListNode(0)\n",
    "        values = list()\n",
    "\n",
    "        while head:\n",
    "            values.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        values.sort()\n",
    "\n",
    "        pre = preHead\n",
    "        \n",
    "        for i in range(len(values)):\n",
    "            pre.next = ListNode(values[i])\n",
    "            pre = pre.next\n",
    "        \n",
    "        return preHead.next\n",
    "\n",
    "\n",
    "\n",
    "        # def sortFunc(head: ListNode, tail: ListNode) -> ListNode:\n",
    "        #     if not head:\n",
    "        #         return head\n",
    "        #     if head.next == tail:\n",
    "        #         head.next = None\n",
    "        #         return head\n",
    "        #     slow = fast = head\n",
    "        #     # slow 会过半\n",
    "        #     while fast != tail:\n",
    "        #         slow = slow.next\n",
    "        #         fast = fast.next\n",
    "        #         if fast != tail:\n",
    "        #             fast = fast.next\n",
    "        #     mid = slow\n",
    "        #     return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "\n",
    "        # def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "        #     preHead = ListNode(0)\n",
    "        #     temp, temp1, temp2 = preHead, head1, head2\n",
    "        #     while temp1 and temp2:\n",
    "        #         if temp1.val <= temp2.val:\n",
    "        #             temp.next = temp1\n",
    "        #             temp1 = temp1.next\n",
    "        #         else:\n",
    "        #             temp.next = temp2\n",
    "        #             temp2 = temp2.next\n",
    "        #         temp = temp.next\n",
    "        #     if temp1:\n",
    "        #         temp.next = temp1\n",
    "        #     elif temp2:\n",
    "        #         temp.next = temp2\n",
    "        #     return preHead.next\n",
    "        \n",
    "        return sortFunc(head, None)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
